/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-02-23
 * Time: 21:40
 */
public class Sort {

    //时间复杂度：O(N+范围)
    //空间复杂度：O(范围)
    //稳定性：稳定
    public static void countSort(int[] array) {
        //1.遍历数组找到最大最小值
        int min = array[0];
        int max = array[0];
        //O(N)
        for (int i = 0; i < array.length; i++) {
            if(min > array[i]) {
                min = array[i];
            }
            if(max < array[i]) {
                max = array[i];
            }
        }
        //2.根据范围定义计数数组长度
        int len = max - min + 1;
        int[] count = new int[len];

        //O(N)
        //3，遍历数组，记录出现次数
        for (int i = 0; i < array.length; i++) {
            count[array[i]-min]++;
        }

        //4，遍历计数数组
        int index = 0;//array数组新下标
        //取决于count.length的大小 O(max-min)
        for (int i = 0; i < count.length; i++) {
            while(count[i] > 0) {
                array[index] = i+min;
                index++;
                count[i]--;
            }
        }

    }
}
